In some computer programs, multiple program threads may execute concurrently on a single system and may access shared memory areas. The interleaved execution of such threads in shared-memory, multi-threaded computing environments may cause one or more of the threads to execute incorrectly. For example, if two threads in a banking application are each configured to execute a withdrawal by first checking for sufficient account balance and then making the withdrawal, then incorrect interleaved execution may result, for instance, if both threads perform the account balance check before either thread withdraws the money, resulting in a negative account balance. Thus, interleaved execution of the two threads may result in incorrect program behavior, commonly known as race conditions, which must be avoided.
Programmers of concurrent systems must take care to avoid inopportune interleavings of concurrent operations. To ensure correctness, programmers often rely on various concurrency control mechanisms, such as synchronization locks. A lock is a software or hardware construct associated with one or more memory areas that is used to control concurrent access to that memory areas among multiple threads. For example, a traditional lock may only be held by one thread at a time and allows that thread exclusive access to one or more memory areas associated with the lock. Other locking protocols and/or implementations exist, such as read/write locks that allow multiple threads to hold the lock concurrently for reading but only one to hold it for writing.
Transactional memory is a concurrent programming paradigm that allows programmers to designate a section of code as atomic. A transactional memory implementation then ensures, via underlying software and/or hardware mechanisms, that such sections are executed atomically (i.e., all at once) with respect to other threads in the system. For instance, in the banking example above, a programmer may designate that the account balance check and the withdrawal operation should be executed together atomically with respect to other threads. Thus, by forbidding the interleaved execution described above, the race condition may be obviated. Transactional memory may be implemented in hardware, software, or a combination thereof.
Transactional Locking (TL) is a software-based, transactional memory (STM) technique that ensures the atomicity of transactions using locks. In traditional TL systems, each memory area that might be accessed within a transaction is mapped by the STM to a single lock that manages concurrency and coordinates access to the associated data areas. Each memory area mapped to a lock may correspond to a respective memory objects (e.g., in object-based systems) or to other arbitrary stripes of memory (e.g., in stripe-based systems).
When a thread in a TL system executes a transaction, the STM ensures that the transaction is executed atomically with respect to other threads in the system. The STM may transparently obtain and release the locks associated with each memory area that is accessed and/or modified by the thread during the transaction. If mutually exclusive, read/write locks, and/or other types of locks are used, the STM normally ensures that each lock is acquired in the proper mode.
Traditional locking STMs tend to perform lock acquisitions and releases often. Therefore, the overhead introduced by these operations may be an important determinant of the system's overall performance. Unfortunately, lock acquisition and release operations are often expensive in traditional implementations. For example, in various traditional schemes, lock acquisition and/or release may necessitate that one or more high-latency atomic instructions, such as a compare-and-swap (CAS) instruction, be executed. Accordingly, considerable effort has been devoted to developing STM algorithms that avoid or reduce the frequency of atomic (e.g., CAS) operations.